home *** CD-ROM | disk | FTP | other *** search
qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk ((((1111 MMMMaaaayyyy 1111999999994444)))) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) NNNNAAAAMMMMEEEE Quantize - ImageMagick's color reduction algorithm. SSSSYYYYNNNNOOOOPPPPSSSSIIIISSSS ####iiiinnnncccclllluuuuddddeeee <<<<mmmmaaaaggggiiiicccckkkk....hhhh>>>> DDDDEEEESSSSCCCCRRRRIIIIPPPPTTTTIIIIOOOONNNN This document describes how IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk performs color reduction on an image. To fully understand this document, you should have a knowledge of basic imaging techniques and the tree data structure and terminology. For purposes of color allocation, an image is a set of _n pixels, where each pixel is a point in RGB space. RGB space is a 3-dimensional vector space, and each pixel, _p , is defined by an ordered triple of red, green, and bl_iue coordinates, (_r , _g , _b ). _i _i _i Each primary color component (red, green, or blue) represents an intensity which varies linearly from 0 to a maximum value, _c , which corresponds to full saturation of that color. Col_mo_ar_xallocation is defined over a domain consisting of the cube in RGB space with opposite vertices at (0,0,0) and (_c ,_c ,_c ). IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk requires _c = _2_5_5. _m_a_x _m_a_x _m_a_x _m_a_x The algorithm maps this domain onto a tree in which each node represents a cube within that domain. In the following discussion, these cubes are defined by the coordinate of two opposite vertices: The vertex nearest the origin in RGB space and the vertex farthest from the origin. The tree's root node represents the the entire domain, (0,0,0) through (_c ,_c ,_c ). Each lower level in the tree is generated _mb_ay_xsu_mb_ad_xivi_md_ai_xng one node's cube into eight smaller cubes of equal size. This corresponds to bisecting the parent cube with planes passing through the midpoints of each edge. The basic algorithm operates in three phases: CCCCllllaaaassssssssiiiiffffiiiiccccaaaattttiiiioooonnnn,,,, RRRReeeedddduuuuccccttttiiiioooonnnn, and AAAAssssssssiiiiggggnnnnmmmmeeeennnntttt. CCCCllllaaaassssssssiiiiffffiiiiccccaaaattttiiiioooonnnn builds a color description tree for the image. RRRReeeedddduuuuccccttttiiiioooonnnn collapses the tree until the number it represents, at most, is the number of colors desired in the output image. AAAAssssssssiiiiggggnnnnmmmmeeeennnntttt defines the output image's color map and sets each pixel's color by reclassification in the reduced tree. Our goal is to minimize the numerical discrepancies between the original colors and quantized colors. To learn more about quantization error, see MEASURING COLOR REDUCTION ERROR later in this document. CCCCllllaaaassssssssiiiiffffiiiiccccaaaattttiiiioooonnnn begins by initializing a color description Page 1 (printed 12/17/98) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk ((((1111 MMMMaaaayyyy 1111999999994444)))) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) tree of sufficient depth to represent each possible input color in a leaf. However, it is impractical to generate a fully-formed color description tree in the classification phase for realistic values of _c . If color components in the input image are quantized t_mo_a_x_k-bit precision, so that _c = _2_k-_1, the tree would need _k levels below the root n_mo_ad_xe to allow representing each possible input color in a leaf. This becomes prohibitive because the tree's total number of nodes is R k i=1 8k A complete tree would require 19,173,961 nodes for _k = _8, _c = _2_5_5. Therefore, to avoid building a fully populated t_mr_ae_xe, IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk: (1) Initializes data structures for nodes only as they are needed; (2) Chooses a maximum depth for the tree as a function of the desired number of colors in the output image (currently _l_o_g (_c_o_l_o_r_m_a_p _s_i_z_e)+_2). A tree of this depth generally allows_4the best representation of the source image with the fastest computational speed and the least amount of memory. However, the default depth is inappropriate for some images. Therefore, the caller can request a specific tree depth. For each pixel in the input image, classification scans downward from the root of the color description tree. At each level of the tree, it identifies the single node which represents a cube in RGB space containing the pixel's color. It updates the following data for each such node: nnnn :::: Number of pixels whose color is contained in the RGB 1111 cube which this node represents; nnnn :::: Number of pixels whose color is not represented in a 2222 node at lower depth in the tree; initially, _n = _0 for all nodes except leaves of the tree. _2 SSSS ,,,, SSSS ,,,, SSSS :::: rrrr ggggSumsbbbbof the red, green, and blue component values for all pixels not classified at a lower depth. The combination of these sums and _n will ultimately characterize the mean color of _2a set of pixels represented by this node. EEEE:::: The distance squared in RGB space between each pixel contained within a node and the nodes' center. This represents the quantization error for a node. RRRReeeedddduuuuccccttttiiiioooonnnn repeatedly prunes the tree until the number of nodes with _n > _0 is less than or equal to the maximum number of co_2lors allowed in the output image. On any given iteration over the tree, it selects those nodes whose _E Page 2 (printed 12/17/98) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk ((((1111 MMMMaaaayyyy 1111999999994444)))) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) value is minimal for pruning and merges their color statistics upward. It uses a pruning threshold, _E , to govern node selection as follows: _p E = 0 wphile number of nodes with (n > 0) > required maximum number of colors 2 prune all nodes such that E <= E Set E to minimum E in remaininpg nodes p This has the effect of minimizing any quantization error when merging two nodes together. When a node to be pruned has offspring, the pruning procedure invokes itself recursively in order to prune the tree from the leaves upward. The values of _n _S , _S , and _S in a node being pruned are always added to_2the_r _g c_borresponding data in that node's parent. This retains the pruned node's color characteristics for later averaging. For each node, _n pixels exist for which that node represents the sm_2allest volume in RGB space containing those pixel's colors. When _n > _0 the node will uniquely define a color in the output i_2mage. At the beginning of reduction, _n = _0 for all nodes except the leaves of the tree which r_2epresent colors present in the input image. The other pixel count, _n , indicates the total number of colors within the cubic _1volume which the node represents. This includes _n - _n pixels whose colors should be defined by nodes at a l_1ower _2level in the tree. AAAAssssssssiiiiggggnnnnmmmmeeeennnntttt generates the output image from the pruned tree. The output image consists of two parts: (1) A color map, which is an array of color descriptions (RGB triples) for each color present in the output image; (2) A pixel array, which represents each pixel as an index into the color map array. First, the assignment phase makes one pass over the pruned color description tree to establish the image's color map. For each node with _n > _0, it divides _S , _S , and _S by _n . This produces the me_2an color of all pix_rels _gthat cla_bssify _2no lower than this node. Each of these colors becomes an entry in the color map. Finally, the assignment phase reclassifies each pixel in the pruned tree to identify the deepest node containing the pixel's color. The pixel's value in the pixel array becomes the index of this node's mean color in the color map. Empirical evidence suggests that distances in color spaces Page 3 (printed 12/17/98) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk ((((1111 MMMMaaaayyyy 1111999999994444)))) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) such as YUV, or YIQ correspond to perceptual color differences more closely than do distances in RGB space. These color spaces may give better results when color reducing an image. Here the algorithm is as described except each pixel is a point in the alternate color space. For convenience, the color components are normalized to the range 0 to a maximum value, _c . The color reduction can then proceed as described. _m_a_x MMMMEEEEAAAASSSSUUUURRRRIIIINNNNGGGG CCCCOOOOLLLLOOOORRRR RRRREEEEDDDDUUUUCCCCTTTTIIIIOOOONNNN EEEERRRRRRRROOOORRRR Depending on the image, the color reduction error may be obvious or invisible. Images with high spatial frequencies (such as hair or grass) will show error much less than pictures with large smoothly shaded areas (such as faces). This is because the high-frequency contour edges introduced by the color reduction process are masked by the high frequencies in the image. To measure the difference between the original and color reduced images (the total color reduction error), IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk sums over all pixels in an image the distance squared in RGB space between each original pixel value and its color reduced value. IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk prints several error measurements including the mean error per pixel, the normalized mean error, and the normalized maximum error. The normalized error measurement can be used to compare images. In general, the closer the mean error is to zero the more the quantized image resembles the source image. Ideally, the error should be perceptually-based, since the human eye is the final judge of quantization quality. These errors are measured and printed when ----vvvveeeerrrrbbbboooosssseeee and ----ccccoooolllloooorrrrssss _a_r_e _s_p_e_c_i_f_i_e_d _o_n _t_h_e _c_o_m_m_a_n_d _l_i_n_e: mmmmeeeeaaaannnn eeeerrrrrrrroooorrrr ppppeeeerrrr ppppiiiixxxxeeeellll:::: is the mean error for any single pixel in the image. nnnnoooorrrrmmmmaaaalllliiiizzzzeeeedddd mmmmeeeeaaaannnn ssssqqqquuuuaaaarrrreeee eeeerrrrrrrroooorrrr:::: is the normalized mean square quantization error for any single pixel in the image. This distance measure is normalized to a range between 0 and 1. It is independent of the range of red, green, and blue values in the image. nnnnoooorrrrmmmmaaaalllliiiizzzzeeeedddd mmmmaaaaxxxxiiiimmmmuuuummmm ssssqqqquuuuaaaarrrreeee eeeerrrrrrrroooorrrr:::: is the largest normalized square quantization error for any single pixel in the image. This distance measure is normalized to a range between 0 and 1. It is independent of the range of red, green, Page 4 (printed 12/17/98) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) IIIImmmmaaaaggggeeeeMMMMaaaaggggiiiicccckkkk ((((1111 MMMMaaaayyyy 1111999999994444)))) qqqquuuuaaaannnnttttiiiizzzzeeee((((9999)))) and blue values in the image. SSSSEEEEEEEE AAAALLLLSSSSOOOO ddddiiiissssppppllllaaaayyyy((((1111)))),,,, aaaannnniiiimmmmaaaatttteeee((((1111)))),,,, mmmmooooggggrrrriiiiffffyyyy((((1111)))),,,, iiiimmmmppppoooorrrrtttt((((1111)))),,,, mmmmiiiiffffffff((((5555)))) CCCCOOOOPPPPYYYYRRRRIIIIGGGGHHHHTTTT Copyright 1998 E. I. du Pont de Nemours and Company Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files ("ImageMagick"), to deal in ImageMagick without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of ImageMagick, and to permit persons to whom the ImageMagick is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of ImageMagick. The software is provided "as is", without warranty of any kind, express or implied, including but not limited to the warranties of merchantability, fitness for a particular purpose and noninfringement. In no event shall E. I. du Pont de Nemours and Company be liable for any claim, damages or other liability, whether in an action of contract, tort or otherwise, arising from, out of or in connection with ImageMagick or the use or other dealings in ImageMagick. Except as contained in this notice, the name of the E. I. du Pont de Nemours and Company shall not be used in advertising or otherwise to promote the sale, use or other dealings in ImageMagick without prior written authorization from the E. I. du Pont de Nemours and Company. AAAACCCCKKKKNNNNOOOOWWWWLLLLEEEEDDDDGGGGEEEEMMMMEEEENNNNTTTTSSSS Paul Raveling, USC Information Sciences Institute, for the original idea of using space subdivision for the color reduction algorithm. With Paul's permission, this document is an adaptation from a document he wrote. AAAAUUUUTTTTHHHHOOOORRRRSSSS John Cristy, E.I. du Pont de Nemours and Company Incorporated Page 5 (printed 12/17/98) 
